package Test.YQNTest;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/9/17 19:12
 * @Description:
 */

public class Graph {
    private static List<Routes> staticRoutesList = Arrays.asList(
//            new Routes(18, "上海", "北京", 3, 45, 305),
            new Routes(21, "上海", "广州", 3, 35, 460),
            new Routes(27, "上海", "成都", 3, 85, 510),
            new Routes(30, "上海", "杭州", 3, 55, 315),
            new Routes(24, "上海", "深圳", 3, 35, 490),
            new Routes(3, "北京", "上海", 3, 40, 300),
            new Routes(6, "北京", "广州", 3, 30, 450),
            new Routes(12, "北京", "成都", 3, 90, 500),
            new Routes(15, "北京", "杭州", 3, 50, 310),
            new Routes(9, "北京", "深圳", 3, 40, 480),
            new Routes(36, "广州", "上海", 3, 30, 465),
            new Routes(33, "广州", "北京", 3, 35, 435)
    );

    public static void main(String[] args) {
        List<City> allCities = City.getAllCities();
        for (City city : allCities) {
            System.out.println("城市: " + city.getName() + ", 编号: " + city.getCode() + ", X坐标: " + city.getX() + ", Y坐标: " + city.getY());
        }
        List<Routes> dijkstra = dijkstra(staticRoutesList, "上海", "北京");
        System.out.println();
        for (Routes r : dijkstra) {
            System.out.println(r);
        }
    }

    public static List<Routes> dijkstra(List<Routes> list, String start, String target) {
        int n = City.getCitiNum();
        //构建邻接矩阵
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (Routes r : list) {
            int x = City.getCityByName(r.getStartPoint()).getCode();
            int y = City.getCityByName(r.getEndPoint()).getCode();
            int weight = r.getTransportTime();
            graph[x].add(new int[]{y, weight});
        }
        // shortestDistances数组保存从起始顶点到其他所有顶点的最短距离
        int[] shortestDistances = new int[n];

        // added数组标记顶点是否已经加入到最短路径树中
        boolean[] added = new boolean[n];

        // 初始化所有距离为无穷大，added数组为false
        for (int vertexIndex = 0; vertexIndex < n; vertexIndex++) {
            shortestDistances[vertexIndex] = Integer.MAX_VALUE;
            added[vertexIndex] = false;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);

        int startCode = City.getCityByName(start).getCode();
        int endCode = City.getCityByName(target).getCode();
        // 起始顶点到自身的距离始终为0
        shortestDistances[startCode] = 0;
        pq.offer(new int[]{0, startCode});


        // parents数组用于存储最短路径树
        int[] parents = new int[n];
        // 起始顶点没有父节点
        parents[startCode] = -1;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[1];
            added[u] = true;

            for (int[] pair : graph[u]) {
                int v = pair[0];
                int weight = pair[1];

                if (!added[v] && shortestDistances[u] != Integer.MAX_VALUE
                        && shortestDistances[u] + weight < shortestDistances[v]) {
                    shortestDistances[v] = shortestDistances[u] + weight;
                    parents[v] = u;
                    pq.offer(new int[]{shortestDistances[v], v});
                }
            }
        }
        // 打印结果
        printSolution(startCode, shortestDistances, parents);

        // 如果需要返回路径，可以在这里构建路径列表

        return buildPath(startCode, endCode, parents, list);
    }
    // 打印构建的距离数组和最短路径
    private static void printSolution(int startVertex, int[] distances, int[] parents) {
        int nVertices = distances.length;
        System.out.print("顶点\t距离\t路径");

        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            if (vertexIndex != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(vertexIndex + "\t\t");
                System.out.print(distances[vertexIndex] + "\t\t");
                printPath(vertexIndex, parents);
            }
        }
    }
    private static void printPath(int currentVertex, int[] parents) {
        if (currentVertex == -1) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    private static List<Routes> buildPath(int startCode, int endCode, int[] parents, List<Routes> routesList) {
        List<Routes> path = new ArrayList<>();
        int current = endCode;
        while (current != startCode) {
            int parent = parents[current];
            for (Routes route : routesList) {
                if (route.getStartPoint().equals(
                        City.values()[parent].getName()
                ) &&
                        route.getEndPoint().equals(
                                City.values()[current].getName())
                ) {
                    path.add(0, route);
                    break;
                }
            }
            current = parent;
        }
        return path;
    }
}
